BASIN_HOPPING

Overview

The BASIN_HOPPING function performs global optimization using the basin-hopping algorithm, a stochastic method designed to find the global minimum of functions with complex, multi-modal landscapes. Originally developed by David Wales and Jonathan Doye for molecular structure optimization, basin-hopping is particularly effective for problems with “funnel-like, but rugged” energy surfaces where many local minima are separated by large barriers.

Basin-hopping is a two-phase iterative algorithm that combines random perturbation with local minimization. Each iteration consists of three steps:

Random displacement: The current position is perturbed by a random step within the specified stepsize
Local minimization: A local optimizer (such as L-BFGS-B or Powell) finds the nearest local minimum
Acceptance decision: The new minimum is accepted or rejected based on the Metropolis criterion

The Metropolis acceptance criterion always accepts steps that decrease the function value. Steps that increase the function value are accepted with probability:

P = \exp\left(-\frac{f(x_{\text{new}}) - f(x_{\text{old}})}{T}\right)

where T is the temperature parameter. Higher temperatures allow the algorithm to escape local minima by accepting uphill moves more frequently. For best results, T should be comparable to the typical difference in function values between local minima.

This implementation uses SciPy’s basinhopping function from the scipy.optimize module. The algorithm was originally described in Wales and Doye’s 1997 paper on Lennard-Jones cluster optimization and has since proven effective across physics, chemistry, and machine learning applications.

The stepsize parameter controls the magnitude of random perturbations—ideally it should match the typical separation between local minima. The function supports multiple local minimization methods including L-BFGS-B (default), Powell, BFGS, Nelder-Mead, and others available through scipy.optimize.minimize.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=BASIN_HOPPING(func_expr, x_zero, niter, T, stepsize, bh_method)

func_expr (str, required): Objective function expression in terms of x (e.g., “x^2 + 10*sin(x)“).
x_zero (float, required): Initial guess for the global minimum.
niter (int, optional, default: 100): Number of basin-hopping iterations.
T (float, optional, default: 1): Temperature parameter controlling acceptance of higher-energy jumps.
stepsize (float, optional, default: 0.5): Step size for random displacement between basins.
bh_method (str, optional, default: “L-BFGS-B”): Local minimization method used within each basin.

Returns (list[list]): 2D list [[x, objective]], or error message string.

Examples

Example 1: Demo case 1

Inputs:

func_expr	x_zero	niter
x**2	5	100

Excel formula:

=BASIN_HOPPING("x**2", 5, 100)

Expected output:

Result
0	0

Example 2: Demo case 2

Inputs:

func_expr	x_zero	niter	T	stepsize
x^2 + 10*sin(x)	0	120	1.5	0.7

Excel formula:

=BASIN_HOPPING("x^2 + 10*sin(x)", 0, 120, 1.5, 0.7)

Expected output:

Result
-1.306	-7.946

Example 3: Demo case 3

Inputs:

func_expr	x_zero	niter	stepsize
exp(-x) * cos(2*x) + x^2/10	2	150	0.5

Excel formula:

=BASIN_HOPPING("exp(-x) * cos(2*x) + x^2/10", 2, 150, 0.5)

Expected output:

Result
1.168	-0.07899

Example 4: Demo case 4

Inputs:

func_expr	x_zero	niter	T	stepsize	bh_method
(x2 - 4)2 + 5cos(2x)	2	200	1	0.5	Powell

Excel formula:

=BASIN_HOPPING("(x**2 - 4)**2 + 5*cos(2*x)", 2, 200, 1, 0.5, "Powell")

Expected output:

Result
1.825	-3.92

Python Code

import math
import re

import numpy as np
from scipy.optimize import basinhopping as scipy_basinhopping

def basin_hopping(func_expr, x_zero, niter=100, T=1, stepsize=0.5, bh_method='L-BFGS-B'):
    """
    Minimize a single-variable expression with SciPy's basinhopping algorithm.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.basinhopping.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        func_expr (str): Objective function expression in terms of x (e.g., "x^2 + 10*sin(x)").
        x_zero (float): Initial guess for the global minimum.
        niter (int, optional): Number of basin-hopping iterations. Default is 100.
        T (float, optional): Temperature parameter controlling acceptance of higher-energy jumps. Default is 1.
        stepsize (float, optional): Step size for random displacement between basins. Default is 0.5.
        bh_method (str, optional): Local minimization method used within each basin. Valid options: L-BFGS-B, Powell, BFGS, Nelder-Mead, TNC, CG, SLSQP. Default is 'L-BFGS-B'.

    Returns:
        list[list]: 2D list [[x, objective]], or error message string.
    """
    if not isinstance(func_expr, str):
        return "Invalid input: func_expr must be a string."
    if func_expr.strip() == "":
        return "Invalid input: func_expr must be a non-empty string."

    func_expr = re.sub(r'\^', '**', func_expr)

    if not re.search(r'\bx\b', func_expr):
        return "Invalid input: func_expr must reference variable x (e.g., x)."

    try:
        x_zero = float(x_zero)
        if not math.isfinite(x_zero):
            return "Invalid input: x_zero must be a finite number."
    except (TypeError, ValueError):
        return "Invalid input: x_zero must be a numeric value."

    try:
        niter = int(niter)
        if niter <= 0:
            return "Invalid input: niter must be a positive integer."
    except (TypeError, ValueError):
        return "Invalid input: niter must be an integer."

    try:
        T = float(T)
        if not math.isfinite(T):
            return "Invalid input: T must be a finite number."
        if T < 0:
            return "Invalid input: T must be non-negative."
    except (TypeError, ValueError):
        return "Invalid input: T must be a numeric value."

    try:
        stepsize = float(stepsize)
        if not math.isfinite(stepsize):
            return "Invalid input: stepsize must be a finite number."
        if stepsize <= 0:
            return "Invalid input: stepsize must be positive."
    except (TypeError, ValueError):
        return "Invalid input: stepsize must be a numeric value."

    if not isinstance(bh_method, str) or bh_method.strip() == "":
        return "Invalid input: bh_method must be a non-empty string."

    safe_globals = {
        "math": math,
        "np": np,
        "numpy": np,
        "__builtins__": {},
    }
    safe_globals.update({
        name: getattr(math, name)
        for name in dir(math)
        if not name.startswith("_")
    })
    safe_globals.update({
        "sin": np.sin,
        "cos": np.cos,
        "tan": np.tan,
        "asin": np.arcsin,
        "arcsin": np.arcsin,
        "acos": np.arccos,
        "arccos": np.arccos,
        "atan": np.arctan,
        "arctan": np.arctan,
        "sinh": np.sinh,
        "cosh": np.cosh,
        "tanh": np.tanh,
        "exp": np.exp,
        "log": np.log,
        "ln": np.log,
        "log10": np.log10,
        "sqrt": np.sqrt,
        "abs": np.abs,
        "pow": np.power,
        "pi": math.pi,
        "e": math.e,
    })

    try:
        initial_eval = eval(func_expr, safe_globals, {"x": x_zero})
        initial_val = float(initial_eval)
        if not math.isfinite(initial_val):
            return "Error: Expression evaluates to non-finite value at initial guess."
    except Exception as exc:
        return f"Error: Invalid expression at initial guess: {exc}"

    def objective(x_value):
        try:
            # Handle numpy arrays by extracting the scalar value
            if isinstance(x_value, np.ndarray):
                x_scalar = float(x_value.item() if x_value.size == 1 else x_value[0])
            else:
                x_scalar = float(x_value)
            result = eval(func_expr, safe_globals, {"x": x_scalar})
            numeric_value = float(result)
        except Exception as exc:
            raise ValueError(f"Error evaluating func_expr: {exc}")
        if not math.isfinite(numeric_value):
            raise ValueError("Objective evaluation produced NaN or infinity.")
        return numeric_value

    try:
        result = scipy_basinhopping(
            objective,
            x_zero,
            niter=niter,
            T=T,
            stepsize=stepsize,
            minimizer_kwargs={"method": bh_method},
        )
        if isinstance(result.x, np.ndarray):
            x_min = float(result.x.item() if result.x.size == 1 else result.x[0])
        else:
            x_min = float(result.x)
        min_val = float(result.fun)

        if not math.isfinite(x_min) or not math.isfinite(min_val):
            return "Error: Optimization produced non-finite results."

        return [[x_min, min_val]]
    except ValueError as exc:
        return f"Error during optimization: {exc}"
    except Exception as exc:
        return f"Error during optimization: {exc}"

Overview

Excel Usage

Examples

Python Code

Online Calculator